package arithmetic1.prim;

import java.util.HashMap;
/*
    普利姆算法:
        求一个图的最小连同子图
 */
public class PrimArithmetic{
    //生成图的最小连同子图,代表当前遍历顶点的索引,flags[i]表示索引为i的顶点是否已经加入到最小生成树中
    //map1用来保存已经选中的边,map2用来保存遍历到但是没有被选中的边
    public static void createMinTree(Graph graph,int n,boolean flags[],HashMap<String,Integer> map1,HashMap<String,Integer> map2){
        //将当前顶点标记为已经遍历
        flags[n]=true;
        //遍历与这个顶点相连的顶点
        for (int j=0;j<graph.peak;j++){
            if(flags[j]==false){    //这个点还没有被遍历
                //将没有遍历到的边添加到map2中
                map2.put(n+"->"+j,graph.matrix[n][j]);
            }
        }
        //记录最小的值
        int minValue=10000;
        //记录最小的值的key
        String minKey="";
        //遍历map2,将map2中最小的边放到map1中
        for(String key:map2.keySet()){
            if(map2.get(key)<minValue){ //最小的边，并且边的两个顶点至少有一个没被遍历到
                int i=Integer.parseInt(key.charAt(0)+"");
                int j=Integer.parseInt(key.charAt(3)+"");
                if(!(flags[i]==true && flags[j]==true)){
                    minValue=map2.get(key);
                    minKey=key;
                }
            }
        }
        if(!minKey.equals("")){ //找到了最小值
            map2.remove(minKey);
            System.out.println(minKey);
            map1.put(minKey,minValue);
            //求出真正的本轮的最小值的索引
            int minIndex=Integer.parseInt(minKey.charAt(3)+"");
            createMinTree(graph,minIndex,flags,map1,map2);
        }
    }
    public static void createMinTree(Graph graph){
        boolean flags[]=new boolean[graph.peak];
        for(int i=0;i<flags.length;i++){
            flags[i]=false;
        }
        //map1用来保存已经选中的边,map2用来保存遍历到但是没有被选中的边
        HashMap<String,Integer> map1=new HashMap<>();
        HashMap<String,Integer> map2=new HashMap<>();
        createMinTree(graph,0,flags,map1,map2);
        int score=0;
        //求出最小生成树的总权值
        for(String key:map1.keySet()){
            score+=map1.get(key);
        }
        System.out.println("总长度为:"+score);
    }

    //普利姆算法,n为第一个加入的顶点的索引
    public static void prim(Graph graph,int n){
        boolean flags[]=new boolean[graph.peak];
        flags[n]=true;  //将该顶点标记为已经加入
        int minValue=10000;
        int h1=-1;  //记录边的第一个顶点
        int h2=-1;  //记录边的第二个顶点
        for(int i=1;i<graph.peak;i++){  //peak个顶点需要加入peak-1条边
            //找到所有已经加入点和它们相连的并且没有加入的顶点形成的边的最小值
            for(int j=0;j<graph.peak;j++){  //遍历已经加入的顶点
                for(int k=0;k<graph.peak;k++){  //遍历没有加入的顶点
                    if(flags[j]==true && flags[k]==false && graph.matrix[j][k]<minValue){
                        minValue=graph.matrix[j][k];
                        h1=j;
                        h2=k;
                    }
                }
            }
            //将加入的点标记为已经加入
            flags[h2]=true;
            System.out.println(h1+"->"+h2+" 长度为:"+minValue);
            minValue=10000;
        }
    }
}

class Graph{
    //图的顶点个数
    int peak;

    //存储图的邻接矩阵
    int matrix[][];

    //存储图的顶点
    String nodes[];

    public Graph(int peak) {
        this.peak = peak;
        nodes=new String[peak];
        matrix=new int[peak][peak];
    }

    //设置图的邻接矩阵
    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    //显示图的邻接矩阵
    public void show(){
        for(int[] arr:matrix){
            for(int value:arr){
                System.out.print(value+"\t");
            }
            System.out.println();
        }
    }
}

class Test{
    public static void main(String[] args) {
        //创建图
        int matrix[][]={{10000,5,7,10000,10000,10000,2},
                        {5,10000,10000,9,10000,10000,3},
                        {7,10000,10000,10000,8,10000,10000},
                        {10000,9,10000,10000,10000,4,10000},
                        {10000,10000,8,10000,10000,5,4},
                        {10000,10000,10000,4,5,10000,6},
                        {2,3,10000,10000,4,6,10000}
        };
        Graph graph=new Graph(7);
        graph.setMatrix(matrix);

        //得到最小生成树信息
//        PrimArithmetic.createMinTree(arithmetic1.graph);

        PrimArithmetic.prim(graph,0);
    }
}
